package com.bascker.algorithm.practice.greed;

import java.util.Objects;

/**
 * 跳跃游戏：
 *   给定一个非负整数数组，最初位于数组的第一个位置 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *   判断是否能够到达最后一个位置。
 *
 * @author bascker
 * @apiNote from leetcode T55
 * @implNote https://gitee.com/bascker/algorithm/wikis/1%E3%80%81%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F?sort_id=2993020
 */
public class Jump {

    public boolean canJump(int[] nums) {
        if (Objects.isNull(nums) || nums.length == 0) {
            return true;
        }

        final int n = nums.length;
        // 动态规划: dp[i] 表示位置 i 能否由初始位置经若干次跳跃到达
        final boolean[] dp = new boolean[n];
        // 初始化 0 号位
        dp[0] = true;

        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                // 若 j 能从初始位置到达，且 j + step 可以跳到 i
                if (dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n - 1];
    }

}
